'''现将待排序的序列划分成若干长度为1的子序列,一次将2个香菱子序列排序后合并成长度为2的子序列'''
# def input_numbers():
#     sort = input('请连续输入偶数个正整数:')
#     li = []
#     for a in sort:
#         li.append(int(a))
#     return li
# def fen(li):
#     '''将输入的数字依次对半拆分,直到拆成一个一个单独的数字'''
#     n = len(li)
#     li1 = []
#     li2 = []
#     count = 0
#     for i in li:
#         count += 1
#         if count <= n/2:
#             li1.append(i)
#         if n/2 < count <= n:
#             li2.append(i)
#     return fen(fen(li))
# print(fen(input_numbers()))
#
#
#
# # print(input_numbers())
# # print(fen(input_numbers()))
def merge_sort(arr):
    # 递归终止条件：数组长度为0或1时直接返回
    if len(arr) <= 1:
        return arr # 直接返回原数组

    # 分解步骤：将数组分成左右两半
    # 计算中间索引（整除确保结果为整数）
    mid = len(arr) // 2 # 例如：len=6 → mid=3
    # 递归分解左半部分（包含索引0到mid-1）
    left = merge_sort(arr[:mid])  # 递归排序左半部分 # 示例：arr[:3] → [6,2,8]
    # 递归分解右半部分（包含索引mid到末尾）
    right = merge_sort(arr[mid:])  # 递归排序右半部分 # 示例：arr[3:] → [5,1,9]
    print(left)
    print(right)

    # 合并步骤
    # 合并已排序的左右部分
    return merge(left, right)


def merge(left, right):
    # 初始化结果列表和双指针
    result = [] # 存储合并后的有序数组
    i = j = 0 # i遍历left，j遍历right（均从0开始）

    # 双指针比较合并（直到某一方遍历完成）
    while i < len(left) and j < len(right):
        # 选择较小元素加入结果
        if left[i] <= right[j]: # 左指针元素更小
            result.append(left[i])
            i += 1 # 左指针右移
        else:
            result.append(right[j]) # 右指针元素更小
            j += 1 # 右指针右移

    # 处理剩余元素（左或右数组有剩余）
    result += left[i:] # 示例：left=[2,6], i=2 → left[i:]为空
    result += right[j:] # 示例：right=[8], j=0 → right[j:]=[8]

    return result
print(merge_sort([3,1,4,1,5,9,2,6]))  # 输出 [1,1,2,3,4,5,6,9]
print(merge_sort([5,3,8,1]))         # 输出 [1,3,5,8]
print(merge_sort([10]))
'''merge_sort([6,2,8,5,1,9])
  │
  ├─ left = merge_sort([6,2,8]) → 分解左半部分
  │    │
  │    ├─ left = merge_sort([6]) → 返回 [6]
  │    │
  │    └─ right = merge_sort([2,8]) 
  │         │
  │         ├─ left = merge_sort([2]) → 返回 [2]
  │         │
  │         └─ right = merge_sort([8]) → 返回 [8]
  │              │
  │              └─ 合并 [2] 和 [8] → [2,8]
  │
  ├─ right = merge_sort([5,1,9]) → 分解右半部分
  │    │
  │    ├─ left = merge_sort([5]) → 返回 [5]
  │    │
  │    └─ right = merge_sort([1,9])
  │         │
  │         ├─ left = merge_sort([1]) → 返回 [1]
  │         │
  │         └─ right = merge_sort([9]) → 返回 [9]
  │              │
  │              └─ 合并 [1] 和 [9] → [1,9]
  │
  └─ 合并左 [2,6,8] 和 右 [1,5,9] → [1,2,5,6,8,9]'''

'''🧩 分步执行细节
阶段1：递归分解（从外到内）
第1层调用 merge_sort([6,2,8,5,1,9])  
mid = 6//2 = 3 → 分解为左子数组 [6,2,8] 和右子数组 [5,1,9]  
暂停当前层，先处理左子数组 merge_sort([6,2,8])
第2层调用 merge_sort([6,2,8])  
mid = 3//2 = 1 → 分解为左 [6] 和右 [2,8]  
暂停，先处理左子数组 merge_sort([6])
第3层调用 merge_sort([6])  
触发终止条件（长度=1）→ 直接返回 [6] → 回到第2层
第2层继续处理右子数组 merge_sort([2,8])  
mid = 2//2 = 1 → 分解为左 [2] 和右 [8]  
暂停，处理左子数组 merge_sort([2])
第4层调用 merge_sort([2])  
直接返回 [2] → 回到第2层的右子处理
第2层继续处理右子数组 merge_sort([8])  
直接返回 [8] → 合并 [2] 和 [8] → [2,8]  
第2层完成 → 返回 merge([6], [2,8]) → [2,6,8]
阶段2：合并过程（从内到外
第1层的左子数组完成 → 得到 [2,6,8]  
开始处理右子数组 merge_sort([5,1,9])
第1层处理右子数组 merge_sort([5,1,9])  
分解逻辑类似左侧，最终合并得到 [1,5,9]
最终合并 
merge([2,6,8], [1,5,9]) → [1,2,5,6,8,9]




🔑 核心特点

递归深度优先：优先分解到最底层，再逐层返回合并  

类似树的后序遍历（先处理子节点，再处理父节点）


合并顺序：最小子数组合并 → 中等子数组合并 → 完整数组合并

空间占用：每次合并需要创建临时数组  

合并 [2] 和 [8] 时创建 [2,8]  
合并 [6] 和 [2,8] 时创建 [2,6,8]'''